import java.util.List;
public class Solution {
    //递归写法
    //当前最小路径和是f(i,j)=f(i+1,j)+f(i+1,j+1)
    //递归时间复杂度高，可以用一个二维数组Integer[][]记录递归过的地方
    Integer[][] arr;
    private int dfs(List<List<Integer>> triangle, int i, int j){

        if(i==triangle.size()){
            return 0;
        }
        if(arr[i][j]!=null){
            return arr[i][j];
        }

        return arr[i][j]=Math.min(dfs(triangle,i+1,j),dfs(triangle,i+1,j+1))+triangle.get(i).get(j);
    }

    public int minimumTotal(List<List<Integer>> triangle) {
        //二维数组初始化
        arr=new Integer[triangle.size()][triangle.size()];
        return dfs(triangle,0,0);

    }
}